#include <bits/stdc++.h>

using namespace std;
const int maxn=10000;
struct node
{
    int data;
    node* lkid;
    node* rkid;
} tree[maxn];

void search_tree(node* root,int x)
{
    if (root==nullptr)
    {
        return;
    }
    if (root->data==x)
    {
        printf("%d",root->data);
    }
    else if (root->data<x)
    {
        search_tree(root->rkid,x);
    }
    else
    {
        search_tree(root->lkid,x);
    }
}
node* findMax(node* root)
{
    while (root->rkid!=nullptr)
    {
        root=root->rkid;
    }
    return root;
}
node* findMin(node* root)
{
    while (root->lkid!=nullptr)
    {
        root=root->lkid;
    }
    return root;
}
void deleteNode(node* &root,int x)
{
    if (root==nullptr)
    {
        return;
    }
    if (root->data==x)
    {
        if (root->lkid==nullptr&&root->rkid==nullptr)
        {
            root=nullptr;
        }
        else if (root->lkid!=nullptr)
        {
            node* pre=findMax(root);
            root->data=pre->data;
            deleteNode(root->lkid,pre->data);
        }
        else
        {
            node* next=findMin(root);
            root->data=next->data;
            deleteNode(root->rkid,next->data);
        }
    }
    else if (root->data<x)
    {
        deleteNode(root->rkid,x);
    }
    else
    {
        deleteNode(root->lkid,x);
    }
}
int main_127()
{

    return 0;
}
